1. Field of the Invention
This invention relates to a division circuit which is capable of performing faster division operation based on a repeat arithmetic operation method using higher radices.
2. Description of the Prior Art
In general, various division methods are well known. One of these division methods is a repeat arithmetic operation method. The repeat arithmetic operation method is explained as follows:
First, a dividend is subtracted from a divisor, then the partial remainder as the result of the subtraction is compared with the divisor in a first stage. In the next stage, an arithmetic operation is determined by the result of the comparison operation. These operations are performed repeatedly at every stage.
FIG. 1 is a schematic diagram of the conventional division circuit based on the repeat arithmetic operation method showing three stage arithmetic operations. In the first stage of the division circuit shown in FIG. 1, a divisor is provided to a complement circuit 1 to obtain a 1's complement of the divisor. A dividend and the 1's complement are input to an adder 2. The output of the adder 2 is provided to a shifter 3. Then, the output of the shifter 3 is input to an adder 12 and a complement circuit 11 in the second stage. These data streams are repeated at every stage.
Thus, the division circuit comprises many arithmetic stages, each arithmetic stage comprising the complement circuit generating the 1's-complement of the divisor, the carry propagation adder (CPA), and the shifter.
In the division circuit having the above configuration, the 1's-complement of the divisor is calculated by the complement circuit 1 in accordance with the value of a sign bit in a shift output of a shifter (not shown) in the preceding stage. Then, the divisor or the 1's complement of the divisor is added to the value of the shifter 3 to get a partial remainder at the CPA 2. Next, the calculated partial remainder is shifted by the shifter 3, then is output to one of the inputs of the following stage. At this time, a sign bit of the partial remainder obtained in this stage is given to one of the inputs of the first stage CPA 2. A dividend is provided to one input terminal of the first stage CPA 2.
As described above, the arithmetic process is performed repeatedly in the sequential stages by receiving the arithmetic result obtained at the preceding stage until a satisfactory quotient is obtained.
A division circuit which is capable of speeding up division by using higher radices is also available.
FIG. 2 is a schematic diagram of the conventional division circuit based on the higher radix division technique, which shows three stage arithmetic operations.
In the division circuit shown in FIG. 2, a value obtained by multiplying a divisor by a constant value at a constant multiplier 41 is provided to one of the input terminals of a CPA 42. A shift output shifted by (Log2 (radix)) is provided to the other input terminal of the CPA 42.
In addition, in the division circuit which uses higher radices (4, 8, 16, . . . ) shown in FIG. 2, a multiple value in each constant multiplier (41, 51, 61, . . . ) is determined based on the result obtained by a comparison operation between a partial remainder as a result of each CPA (42, 52, 62, . . . ) operation and each constant multiple of a divisor. A plurality of the constant multiple values is provided to each stage, (as shown in FIG. 2, the divisor x Ca, the divisor x Cb, . . . ).
Accordingly, in the division circuit shown in FIG. 2 the determining operation described above is operated by a plurality of comparators 44, 45, . . . , and 54, 55, . . . in the first and the second stages. The result of each comparison operation in each stage is provided as a quotient to a quotient register (not shown) and the constant multiplier in the following stage. Thereby, at each constant multiplier (41, 51, 61, . . . ) the divisor is multiplied by a specified multiple value.
Moreover, in the division circuit using the higher radices, not all bits of the divisor and all bits of the dividend are required for the comparison operation between the partial remainder and the constant multiple value of the divisor. The number of bits of the divisor and the dividend required for the comparison operation is less than the total number of bits of the divisor and the dividend. A satisfactory number of bits for the divisor and the dividend is the number of bits by which the arithmetic operation converges in the following stage. Thus, the increasing of the comparator configuration can be stopped even if the number of the bits of the divisor or the dividend increases.
Therefore a quotient having a plurality of bits is obtained at each stage in a division circuit using higher radices and the number of stages can be reduced so that a higher speed division calculation can be achieved in a smaller size division circuit.
In the conventional division circuit, as described above in detail, an addition operation is a main arithmetic operation in each stage. The addition operation is carried out by a carry propagation adder (CPA) 2 in which a carry is propagated to the upper side. Accordingly, much time is required for the carry propagation in each stage when the data length of a divisor and a dividend become long. This causes a reduced addition operation in each stage of the division circuit.
Therefore the total speed of the division circuit is further increased. This is a problem.